UVa/11506 - Angry Programmer/angry.cpp

   1 /*
   2   Problem: A - Angry programmer
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Accepted
   7  */
   8
   9 using namespace std;
  10 #include <algorithm>
  11 #include <iostream>
  12 #include <iterator>
  13 #include <sstream>
  14 #include <fstream>
  15 #include <cassert>
  16 #include <climits>
  17 #include <cstdlib>
  18 #include <cstring>
  19 #include <string>
  20 #include <cstdio>
  21 #include <vector>
  22 #include <cmath>
  23 #include <queue>
  24 #include <deque>
  25 #include <stack>
  26 #include <map>
  27 #include <set>
  28
  29 #define D(x) cout << #x " is " << x << endl
  30
  31 const int MAXN = 2*55;
  32
  33 int cap[MAXN+1][MAXN+1], flow[MAXN+1][MAXN+1], prev[MAXN+1];
  34
  35 /*
  36   cap[i][j] = Capacidad de la arista (i, j).
  37   flow[i][j] = Flujo actual de i a j.
  38   prev[i] = Predecesor del nodo i en un camino de aumentación.
  39  */
  40
  41 int fordFulkerson(int n, int s, int t){
  42   int ans = 0;
  43   for (int i=0; i<n; ++i) fill(flow[i], flow[i]+n, 0);
  44   while (true){
  45     fill(prev, prev+n, -1);
  46     queue<int> q;
  47     q.push(s);
  48     while (q.size() && prev[t] == -1){
  49       int u = q.front();
  50       q.pop();
  51       for (int v = 0; v<n; ++v)
  52         if (v != s && prev[v] == -1 && cap[u][v] - flow[u][v] > 0 )
  53           prev[v] = u, q.push(v);
  54     }
  55
  56     if (prev[t] == -1) break;
  57
  58     int bottleneck = INT_MAX;
  59     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  60       bottleneck = min(bottleneck, cap[u][v] - flow[u][v]);
  61     }
  62     for (int v = t, u = prev[v]; u != -1; v = u, u = prev[v]){
  63       flow[u][v] += bottleneck;
  64       flow[v][u] = -flow[u][v];
  65     }
  66     ans += bottleneck;
  67   }
  68   return ans;
  69 }
  70
  71
  72 inline int in(int i){ return 2*i; }
  73 inline int out(int i){ return 2*i+1; }
  74
  75 int main(){
  76   //assert(freopen("angry.in", "r", stdin) != NULL);
  77   int n, e;
  78   while (cin >> n >> e && (n+e)){
  79     memset(cap, 0, sizeof cap);
  80
  81      //Las dos máquinas que no pueden ser destruídas.
  82     cap[in(0)][out(0)] = cap[in(n-1)][out(n-1)]= INT_MAX;
  83
  84
  85     //Costo de destrucción de máquinas.
  86     for (int k=2, i, w; k<n; ++k){
  87       cin >> i >> w; --i;
  88       cap[in(i)][out(i)] = w;
  89     }
  90
  91     //Costo de destrucción de cables.
  92     for (int k=0, i, j, w; k<e; ++k){
  93       cin >> i >> j >> w; --i, --j;
  94       cap[out(i)][in(j)] = cap[out(j)][in(i)] = w;
  95     }
  96     int ans = fordFulkerson(2*n, in(0), out(n-1));
  97     cout << ans << endl;
  98   }
  99   return 0;
 100 }